package exp1dtree.dtree;

import java.util.List;

import exp1dtree.record.Record;

public final class DTree {

	public static enum Strategy {
		NO, PRE, POST
	}
	
	public static List<Record> trainList;
	public static List<Record> validationList;
	public static boolean[] able;
	
	private int size;
	private int attID;
	private DTree[] child;
	private boolean isLeaf;
	private boolean guess;
	private int hit;
	
	public DTree() {
		size = 1;
		hit = 0;
		isLeaf = true;
		guess = false;
	}
	
	private boolean isSameOutput(int l, int r) {
		guess = trainList.get(l).isPositive();
		int cnt = 1;
		for (int i = l + 1; i < r; ++i) {
			if (trainList.get(i).isPositive() != guess)
				--cnt;
			else
				++cnt;
		}
		if (cnt < 0)
			guess = !guess;
		return (cnt == r - l);
	}
	
	private boolean isSameInput(int l, int r) {
		Record a = trainList.get(l);
		for (int i = l + 1; i < r; ++i) {
			if (!trainList.get(i).isSameInput(a))
				return false;
		}
		return true;
	}
	
	private void quickSortTrain(int l, int r) {
		int i = l;
		int j = r;
		Record mid = trainList.get((l + r) / 2);
		do {
			while (trainList.get(i).lessThan(mid, attID))
				++i;
			while (mid.lessThan(trainList.get(j), attID))
				--j;
			if (i <= j) {
				java.util.Collections.swap(trainList, i, j);
				++i;
				--j;
			}
		} while (i <= j);
		if (i < r)
			quickSortTrain(i, r);
		if (l < j)
			quickSortTrain(l, j);
	}
	
	private double getPairEntropy(int pos, int neg) {
		if (pos == 0 || neg == 0)
			return 0;
		double p = pos * 1.0 / (pos + neg);
		double q = 1 - p;
		return - p * java.lang.Math.log(p) - q * java.lang.Math.log(q);
	}
	
	private double getEntropy(int l, int r, int id) {
		int[] cntPos = new int[Record.disCnt[id]];
		int[] cntNeg = new int[Record.disCnt[id]];
		for (int i = l; i < r; ++i) {
			if (trainList.get(i).isPositive())
				++cntPos[trainList.get(i).getAtt(id)];
			else
				++cntNeg[trainList.get(i).getAtt(id)];
		}
		double entropy = 0;
		for (int i = 0; i < Record.disCnt[id]; ++i)
			entropy += getPairEntropy(cntPos[i], cntNeg[i]) * (cntPos[i] + cntNeg[i]);
		return entropy / (r - l);
	}
	
	private void calcAttID(int l, int r) {
		double bestEntropy = 2;
		for (int i = 0; i < Record.attCnt; ++i)
			if (able[i]) {
				double newEntropy = getEntropy(l, r, i);
				if (newEntropy < bestEntropy) {
					bestEntropy = newEntropy;
					attID = i;
				}
			}
	}
	
	public void build(int l, int r, Strategy s) {
		if (isSameOutput(l, r))
			return;
		if (isSameInput(l, r))
			return;
		calcAttID(l, r);
		isLeaf = false;
		able[attID] = false;
		quickSortTrain(l, r - 1);
		child = new DTree[Record.disCnt[attID]];
		for (int i = l; i < r; ) {
			int iAtt = trainList.get(i).getAtt(attID);
			int j = i + 1;
			while ((j < r) && (trainList.get(j).getAtt(attID) == iAtt))
				++j;
			child[iAtt] = new DTree();
			child[iAtt].build(i, j, s);
			size += child[iAtt].size;
			i = j;
		}
		able[attID] = true;
	}
	
	private void quickSortValid(int l, int r) {
		int i = l;
		int j = r;
		Record mid = validationList.get((l + r) / 2);
		do {
			while (validationList.get(i).lessThan(mid, attID))
				++i;
			while (mid.lessThan(validationList.get(j), attID))
				--j;
			if (i <= j) {
				java.util.Collections.swap(validationList, i, j);
				++i;
				--j;
			}
		} while (i <= j);
		if (i < r)
			quickSortValid(i, r);
		if (l < j)
			quickSortValid(l, j);
	}
	
	public void postPrune(int l, int r) {
		if (isLeaf) {
			for (int i = l; i < r; ++i)
				if (guess == validationList.get(i).isPositive())
					++hit;
			return;
		}
		
		if (r - l > 1)
			quickSortValid(l, r - 1);
		for (int i = l; i < r; ) {
			int iAtt = validationList.get(i).getAtt(attID);
			int j = i + 1;
			while ((j < r) && (validationList.get(j).getAtt(attID) == iAtt))
				++j;

			if (child[iAtt] == null) {
				for (int k = i; k < j; ++k) {
					if (guess == validationList.get(k).isPositive())
						++hit;
				}
				i = j;
				continue;
			}

			child[iAtt].postPrune(i, j);
			
			int newHit = 0;
			for (int k = i; k < j; ++k) {
				Record rr = validationList.get(k);
				if (guess == rr.isPositive())
					++newHit;
			}
			if (newHit > child[iAtt].hit) {
				child[iAtt] = null;
				hit += newHit;
			}

			i = j;
		}
		
		size = 1;
		for (int i = 0; i < child.length; ++i)
			if (child[i] != null) {
				hit += child[i].hit;
				size += child[i].size;
			}
		isLeaf = (size == 1);
	}
	
	public boolean simulate(Record r) {
		if (isLeaf)
			return guess;
		else {
			if (child[r.getAtt(attID)] != null)
				return child[r.getAtt(attID)].simulate(r);
//			else if (child[0] != null)
//				return child[0].simulate(r);
			else
				return guess;
				
		}
	}
	
	public int getSize() {
		return size;
	}

}
